# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

    def __str__(self):
        return str(self.val)


def meet(fast: ListNode, slow: ListNode):
    first = True
    while fast and (fast != slow or first):
        if fast == slow and not first:
            break
        first = False
        if fast.next is None:
            fast = None
            break
        if fast.next == slow:
            fast = fast.next.next
            break
        fast = fast.next.next
        slow = slow.next
    return fast


class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return None
        fast = meet(head, head)
        if fast is None:
            return None
        while fast != head:
            fast = fast.next
            head = head.next
        return fast


def build(nodes, pos):
    print(nodes)
    a = []
    for val in nodes:
        a.append(ListNode(val))

    for i in range(len(a) - 1):
        a[i].next = a[i + 1]

    if pos != -1:
        a[-1].next = a[pos]
    return a[0]


if __name__ == '__main__':
    so = Solution()
    head = build([0, 1, 2, 3, 4, 5, 6, 7, 8], 2)
    re = so.detectCycle(head)
    print(re)
